{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Increment Operations to Make Array Beautiful"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minIncrementOperations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #使数组变美的最小增量运算数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong> 开始、长度为 <code>n</code> 的整数数组 <code>nums</code> ，和一个整数 <code>k</code> 。</p>\n",
    "\n",
    "<p>你可以执行下述 <strong>递增</strong> 运算 <strong>任意</strong> 次（可以是 <strong>0</strong> 次）：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>从范围&nbsp;<code>[0, n - 1]</code> 中选择一个下标 <code>i</code> ，并将 <code>nums[i]</code> 的值加 <code>1</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>如果数组中任何长度 <strong>大于或等于 3</strong> 的子数组，其 <strong>最大</strong> 元素都大于或等于 <code>k</code> ，则认为数组是一个 <strong>美丽数组</strong> 。</p>\n",
    "\n",
    "<p>以整数形式返回使数组变为 <strong>美丽数组</strong> 需要执行的 <strong>最小</strong> 递增运算数。</p>\n",
    "\n",
    "<p>子数组是数组中的一个连续 <strong>非空</strong> 元素序列。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [2,3,0,0,2], k = 4\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>可以执行下述递增运算，使 nums 变为美丽数组：\n",
    "选择下标 i = 1 ，并且将 nums[1] 的值加 1 -&gt; [2,4,0,0,2] 。\n",
    "选择下标 i = 4 ，并且将 nums[4] 的值加 1 -&gt; [2,4,0,0,3] 。\n",
    "选择下标 i = 4 ，并且将 nums[4] 的值加 1 -&gt; [2,4,0,0,4] 。\n",
    "长度大于或等于 3 的子数组为 [2,4,0], [4,0,0], [0,0,4], [2,4,0,0], [4,0,0,4], [2,4,0,0,4] 。\n",
    "在所有子数组中，最大元素都等于 k = 4 ，所以 nums 现在是美丽数组。\n",
    "可以证明无法用少于 3 次递增运算使 nums 变为美丽数组。\n",
    "因此，答案为 3 。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [0,1,3,3], k = 5\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>可以执行下述递增运算，使 nums 变为美丽数组：\n",
    "选择下标 i = 2 ，并且将 nums[2] 的值加 1 -&gt; [0,1,4,3] 。\n",
    "选择下标 i = 2 ，并且将 nums[2] 的值加 1 -&gt; [0,1,5,3] 。\n",
    "长度大于或等于 3 的子数组为 [0,1,5]、[1,5,3]、[0,1,5,3] 。\n",
    "在所有子数组中，最大元素都等于 k = 5 ，所以 nums 现在是美丽数组。\n",
    "可以证明无法用少于 2 次递增运算使 nums 变为美丽数组。 \n",
    "因此，答案为 2 。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,1,2], k = 1\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>在这个示例中，只有一个长度大于或等于 3 的子数组 [1,1,2] 。\n",
    "其最大元素 2 已经大于 k = 1 ，所以无需执行任何增量运算。\n",
    "因此，答案为 0 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>3 &lt;= n == nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li><code>0 &lt;= k &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-increment-operations-to-make-array-beautiful](https://leetcode.cn/problems/minimum-increment-operations-to-make-array-beautiful/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-increment-operations-to-make-array-beautiful](https://leetcode.cn/problems/minimum-increment-operations-to-make-array-beautiful/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,3,0,0,2]\\n4', '[0,1,3,3]\\n5', '[1,1,2]\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementOperations(self, nums: List[int], k: int) -> int:\n",
    "        \n",
    "        n = len(nums)\n",
    "        \n",
    "        @cache\n",
    "        def dp(i, cover):\n",
    "            if i >= n:\n",
    "                return 0\n",
    "            \n",
    "            ans = float(\"inf\")\n",
    "            if cover > 0:\n",
    "                if nums[i] >= k:\n",
    "                    return dp(i+1, 2)\n",
    "                else:\n",
    "                    return min(dp(i+1, cover-1), k - nums[i] + dp(i+1, 2))\n",
    "            else:\n",
    "                if nums[i] >= k:\n",
    "                    return dp(i+1, 2)\n",
    "                else:\n",
    "                    return k - nums[i] + dp(i+1, 2)\n",
    "            \n",
    "            # return ans\n",
    "        \n",
    "        \n",
    "        return dp(0, 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementOperations(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        f0 = f1 = f2 = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            inc = f0 + max(k-x, 0)\n",
    "            f0 = min(inc, f1)\n",
    "            f1 = min(inc, f2)\n",
    "            f2 = inc\n",
    "\n",
    "        return f0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left, bisect_right, insort_left, insort_right, insort, bisect\n",
    "from math import ceil, floor, pow, gcd, sqrt, log10, fabs, fmod, factorial, inf, pi, e\n",
    "from heapq import heapify, heapreplace, heappush, heappop, heappushpop, nlargest, nsmallest\n",
    "from collections import defaultdict, Counter, deque\n",
    "from itertools import permutations, combinations, combinations_with_replacement, accumulate, count, groupby, pairwise\n",
    "from queue import PriorityQueue, Queue, LifoQueue\n",
    "from functools import lru_cache, cache, reduce\n",
    "from typing import List, Optional\n",
    "import sys\n",
    "\n",
    "from sortedcontainers import SortedList, SortedDict, SortedSet\n",
    "\n",
    "sys.setrecursionlimit(10001000)\n",
    "\n",
    "MOD = int(1e9 + 7)\n",
    "INF = int(1e20)\n",
    "INFMIN = float('-inf')  # 负无穷\n",
    "INFMAX = float('inf')  # 正无穷\n",
    "PI = 3.141592653589793\n",
    "direc = [(1, 0), (0, 1), (-1, 0), (0, -1)]\n",
    "direc8 = [(1, 0), (0, 1), (-1, 0), (0, -1), (1, 1), (1, -1), (-1, 1), (-1, -1)]\n",
    "ALPS = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'\n",
    "alps = 'abcdefghijklmnopqrstuvwxyz'\n",
    "\n",
    "'''\n",
    "gcd(), ord(), chr(), lower(), upper() 最大公约数/ASCII字符数值/数值ASCII字符/小写/大写\n",
    "startswith(s), endswith(s), find(), index(), count(s)  字符串是否以s开始的/字符串是否以s结尾的/查找返回的是索引/获取索引\n",
    "isalpha(), isdigit(), space(),join()  判断是否全为字符/判断是否全为数字/判断是否为空格/拼接\n",
    "eval() 字符串转换成列表、元组或者字典/\n",
    "uniform(x, y), pow(x, y)# 随机生成下一个实数，它在[x,y]范围内/ x**y 运算后的值。\n",
    "字典推倒式 {key: len(key) for key in list}\n",
    "列表推倒式 [i for i in range(100) if i % 3 == 0] 可切片,可索引,可重复\n",
    "集合推倒式 {i ** 2 for i in (1, 2, 3)}  不可索引,不可切片,不可重复元素\n",
    "'''\n",
    "\n",
    "# 数值和字母进行转换 ord()函数是把字符转换成ASCII码 chr()函数是把ASCII码转换成字符\n",
    "def alp(i):\n",
    "    return chr(ord('a') + i % 26)  # i=0->'a', i=25->'z'\n",
    "\n",
    "# lcm 最小公倍数 gcd 最大公约数\n",
    "def lcm(x, y):\n",
    "    return x * y // gcd(x, y)\n",
    "\n",
    "# 快速幂\n",
    "def qpow(x, y):\n",
    "    ans = 1\n",
    "    while y:\n",
    "        if y & 1:\n",
    "            ans *= x\n",
    "        x *= x\n",
    "        y >>= 1\n",
    "    return ans\n",
    "\n",
    "# 求组合数\n",
    "def Comb(n, m, p):\n",
    "    a = (factorial(n)) % p\n",
    "    b = (qpow(factorial(m), (p - 2), p)) % p\n",
    "    c = (qpow(factorial(n - m), (p - 2), p)) % p\n",
    "    return a * b * c % p\n",
    "\n",
    "# lucas求组合数\n",
    "def Lucas(n, m, p):\n",
    "    if m == 0:\n",
    "        return 1\n",
    "    return Comb(n % p, m % p, p) * Lucas(n // p, m // p, p) % p\n",
    "\n",
    "def rep():\n",
    "    a = list(map(int, input().split()))\n",
    "    return a\n",
    "\n",
    "def sep():\n",
    "    a = input().rstrip('\\n')\n",
    "    return a\n",
    "\n",
    "# --idea \n",
    "# -*- coding: utf-8 -*-\n",
    "# @Author  : hakusai\n",
    "# @Time    : 2023/11/26 17:14\n",
    "class Solution:\n",
    "    def minIncrementOperations(self, nums: List[int], k: int) -> int:\n",
    "        f0 = f1 = f2 = 0\n",
    "        for x in nums:\n",
    "            inc = f0 + max(k - x, 0)\n",
    "            f0 = min(inc, f1)\n",
    "            f1 = min(inc, f2)\n",
    "            f2 = inc\n",
    "        return f0\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    print(Solution.minIncrementOperations(self=None, nums=[2, 3, 0, 0, 2], k=4))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementOperations(self, nums: List[int], k: int) -> int:\n",
    "        if len(nums)<=2:\n",
    "            return 0 \n",
    "\n",
    "        f=[[0,0] for i in range(len(nums)+1)]\n",
    "        \n",
    "        \n",
    "\n",
    "        max_=-1\n",
    "\n",
    "        last_three=[nums[0],nums[1]]\n",
    "\n",
    "        f[1]=[0, 0 if nums[0]>=k else k-nums[0]]\n",
    "        f[2]=[0,0 if nums[1]>=k else k-nums[1]]\n",
    "\n",
    "\n",
    "        for i in range(3,len(nums)+1):\n",
    "            index=i-1\n",
    "            f[i][0]=min(f[i-1][1],f[i-2][1])\n",
    "            f[i][1]=(0 if nums[index]>=k else k-nums[index])+min(min(f[i-1][1],f[i-2][1]),f[i-3][1])\n",
    "            #print(f)\n",
    "        return min(f[len(nums)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementOperations(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        f = [[0] * 3 for _ in range(n+1)]\n",
    "        for i, x in enumerate(nums):\n",
    "            for j in range(3):\n",
    "                f[i+1][j] = f[i][0] + max(k-x, 0)\n",
    "                if j < 2:\n",
    "                    f[i+1][j] = min(f[i+1][j], f[i][j+1])\n",
    "\n",
    "        return f[n][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementOperations(self, nums: List[int], k: int) -> int:\n",
    "        '''\n",
    "        @cache\n",
    "        def dfs(i: int, j: int) -> int:\n",
    "            if i < 0:\n",
    "                return 0\n",
    "            res = dfs(i - 1, 0) + max(k - nums[i], 0)  # nums[i] 增大\n",
    "            if j < 2:\n",
    "                res = min(res, dfs(i - 1, j + 1))  # nums[i] 不增大\n",
    "            return res\n",
    "        '''\n",
    "        n=len(nums)\n",
    "        f=[[inf]*3 for _ in range(n+1)]\n",
    "        f[0]=[0,0,0]\n",
    "        for i in range(n):\n",
    "            for j in range(3):\n",
    "                f[i+1][j]=f[i][0]+max(k-nums[i],0)\n",
    "                if j<2:\n",
    "                    f[i+1][j]=min(f[i+1][j],f[i][j+1])\n",
    "        \n",
    "        return f[n][0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def minIncrementOperations(self, nums: List[int], k: int) -> int:\n",
    "        n=len(nums)\n",
    "        i=0\n",
    "        sl=SortedList()\n",
    "        while i<3:\n",
    "            sl.add([nums[i],i])\n",
    "            i+=1\n",
    "        ans,preindex,premax=0,-1,-1\n",
    "        ans+=max(0,k-sl[-1][0])\n",
    "        preindex=sl[-1][1]\n",
    "        premax=k\n",
    "        while i<n:\n",
    "            sl.discard([nums[i-3],i-3])\n",
    "            sl.add([nums[i],i])\n",
    "            if i-3==preindex:\n",
    "                ans+=max(0,k-sl[-1][0])\n",
    "                preindex=sl[-1][1]\n",
    "                premax=k\n",
    "            i+=1\n",
    "        return ans\n",
    "\n",
    "# dp[i][0] 表示i不变,i-1不变,i-2变\n",
    "# dp[i][1] 表示i不变,i-1变,i-2不变\n",
    "# dp[i][2] 表示i不变,i-1变,i-2变\n",
    "# dp[i][3] 表示i变,i-1不变,i-2不变\n",
    "# dp[i][4] 表示i变,i-1不变,i-2变\n",
    "# dp[i][5] 表示i变,i-1变,i-2不变\n",
    "# dp[i][6] 表示i变,i-1变,i-2变\n",
    "class Solution:\n",
    "    def minIncrementOperations(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        dp=[[0]*7 for _ in range(n)]\n",
    "        dp[0][0]=0\n",
    "        dp[0][1]=0\n",
    "        dp[0][2]=0\n",
    "        dp[0][3]=max(0,k-nums[0])\n",
    "        dp[0][4]=max(0,k-nums[0])\n",
    "        dp[0][5]=max(0,k-nums[0])\n",
    "        dp[0][6]=max(0,k-nums[0])\n",
    "\n",
    "        dp[1][0]=0\n",
    "        dp[1][1]=max(0,k-nums[0])\n",
    "        dp[1][2]=max(0,k-nums[0])\n",
    "        dp[1][3]=max(0,k-nums[1])\n",
    "        dp[1][4]=max(0,k-nums[1])\n",
    "        dp[1][5]=max(0,k-nums[1])+max(0,k-nums[0])\n",
    "        dp[1][6]=max(0,k-nums[1])+max(0,k-nums[0])    \n",
    "        for i in range(2,n):\n",
    "            dp[i][0]=min(dp[i-1][1],dp[i-1][2])\n",
    "            dp[i][1]=min(dp[i-1][3],dp[i-1][4])\n",
    "            dp[i][2]=min(dp[i-1][5],dp[i-1][6])\n",
    "            dp[i][3]=max(0,k-nums[i])+dp[i-1][0]\n",
    "            dp[i][4]=max(0,k-nums[i])+min(dp[i-1][1],dp[i-1][2])\n",
    "            dp[i][5]=max(0,k-nums[i])+min(dp[i-1][3],dp[i-1][4])\n",
    "            dp[i][6]=max(0,k-nums[i])+min(dp[i-1][5],dp[i-1][6])\n",
    "        return min(dp[n-1])\n",
    "\n",
    "# 缩减状态\n",
    "# dp[i][0] 表示i不变,i-1不变\n",
    "# dp[i][1] 表示i不变,i-1变\n",
    "# dp[i][2] 表示i变,i-1不变\n",
    "# dp[i][3] 表示i变,i-1变\n",
    "class Solution:\n",
    "    def minIncrementOperations(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        dp=[[0]*7 for _ in range(n)]\n",
    "        dp[0][0]=0\n",
    "        dp[0][1]=0\n",
    "        dp[0][2]=0\n",
    "        dp[0][3]=max(0,k-nums[0])\n",
    "        dp[0][4]=max(0,k-nums[0])\n",
    "        dp[0][5]=max(0,k-nums[0])\n",
    "        dp[0][6]=max(0,k-nums[0])\n",
    "\n",
    "        # dp[1][0]=0\n",
    "        # dp[1][1]=max(0,k-nums[0])\n",
    "        # dp[1][2]=max(0,k-nums[0])\n",
    "        # dp[1][3]=max(0,k-nums[1])\n",
    "        # dp[1][4]=max(0,k-nums[1])\n",
    "        # dp[1][5]=max(0,k-nums[1])+max(0,k-nums[0])\n",
    "        # dp[1][6]=max(0,k-nums[1])+max(0,k-nums[0])    \n",
    "        for i in range(1,n):\n",
    "            dp[i][0]=min(dp[i-1][1],dp[i-1][2])\n",
    "            dp[i][1]=min(dp[i-1][3],dp[i-1][4])\n",
    "            dp[i][2]=min(dp[i-1][5],dp[i-1][6])\n",
    "            dp[i][3]=max(0,k-nums[i])+dp[i-1][0]\n",
    "            dp[i][4]=max(0,k-nums[i])+min(dp[i-1][1],dp[i-1][2])\n",
    "            dp[i][5]=max(0,k-nums[i])+min(dp[i-1][3],dp[i-1][4])\n",
    "            dp[i][6]=max(0,k-nums[i])+min(dp[i-1][5],dp[i-1][6])\n",
    "        return min(dp[n-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementOperations(self, nums: List[int], k: int) -> int:\n",
    "        @cache\n",
    "        def f(i):\n",
    "            if i < 2: return 0\n",
    "            return min(f(j-1)+max(0,k-nums[j]) for j in range(i-2,i+1))\n",
    "        return f(len(nums)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementOperations(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [[inf] * 3 for i in range(n)]\n",
    "\n",
    "        def dfs(i, j: int) -> int:\n",
    "            if i < 0:\n",
    "                return 0\n",
    "            if dp[i][j] != inf:\n",
    "                return dp[i][j]\n",
    "            res = dfs(i-1, 0) + max(k - nums[i], 0)     \n",
    "            if nums[i] < k and j < 2:\n",
    "                res = min(dfs(i-1, j+1), res)\n",
    "            dp[i][j] = res\n",
    "            return res\n",
    "        \n",
    "        return dfs(n-1, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementOperations(self, nums: List[int], k: int) -> int:\n",
    "        n=len(nums)\n",
    "        F=[[-1,-1,-1] for _ in range(n)]\n",
    "        def f(i,j):\n",
    "            if i<0:\n",
    "                return 0\n",
    "            if F[i][j] !=-1:\n",
    "                return F[i][j]\n",
    "            if nums[i]>=k:\n",
    "                res=f(i-1,0)\n",
    "            else:\n",
    "                res=f(i-1,0)+k-nums[i]\n",
    "                if j<2:\n",
    "                    res=min(res,f(i-1,j+1))\n",
    "            F[i][j]=res\n",
    "            return res\n",
    "        return f(n-1,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementOperations(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i>=n: return 0\n",
    "            if i>=n-3:\n",
    "                return max(0,-nums[i]+k)\n",
    "            res1=min(dfs(i+3),dfs(i+2),dfs(i+1))\n",
    "            if nums[i]<k: # 改\n",
    "                res1 += k-nums[i]\n",
    "            return res1 \n",
    "        return min(dfs(0),dfs(1),dfs(2))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def minIncrementOperations(self, nums: List[int], k: int) -> int:\n",
    "        mem = [-1 for i in range(len(nums) + 1)]\n",
    "        def search(nums: List[int], k: int,idx):\n",
    "            if idx + 2 >= len(nums) :\n",
    "                return 0\n",
    "            if len(nums) == 3:\n",
    "                return max(k - max(nums),0)\n",
    "            if mem[idx] != -1:\n",
    "                return mem[idx]\n",
    "            result = min(\n",
    "                max(k - nums[idx] , 0) + search(nums,k,idx+1),\n",
    "                max(k - nums[idx+1] , 0) + search(nums,k,idx+2),\n",
    "                max(k - nums[idx+2] , 0) + search(nums,k,idx+3)\n",
    "            )\n",
    "            mem[idx] = result\n",
    "            return result\n",
    "        \n",
    "        ret = search(nums,k,0)\n",
    "        \n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementOperations(self, nums: List[int], k: int) -> int:\n",
    "        dp=[None]*(len(nums)+1)\n",
    "        def find(n):\n",
    "            if dp[n]!=None:\n",
    "                return dp[n]\n",
    "            if n<=0:\n",
    "                return 0\n",
    "            dp[n]=min(find(n-1),find(n-2),find(n-3))+max(k-nums[n-1],0)\n",
    "            return dp[n]\n",
    "        return min(find(len(nums)),find(len(nums)-1),find(len(nums)-2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementOperations(self, nums: List[int], k: int) -> int:\n",
    "        \n",
    "        n = len(nums)\n",
    "        @lru_cache()\n",
    "        def f(i, now):\n",
    "            if now <= 0:\n",
    "                return 0\n",
    "            t1 = max(0, k-nums[i])\n",
    "            t1 = t1 + f(i-1, i-2)\n",
    "            \n",
    "            t2 = float('inf')\n",
    "            if now <= i:\n",
    "                t2 = f(i-1, now)\n",
    "            return min(t1, t2)\n",
    "        ans = f(n-1, n-2)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementOperations(self, nums: List[int], k: int) -> int:\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i >= len(nums):\n",
    "                return 0\n",
    "            return max(0, k - nums[i]) + min(dfs(i + 1), dfs(i + 2), dfs(i + 3))\n",
    "        res = min(dfs(0), dfs(1), dfs(2))\n",
    "        dfs.cache_clear()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementOperations(self, nums: List[int], k: int) -> int:       \n",
    "        n = len(nums)\n",
    "        f = [[-inf] * 3 for _ in range(n + 1)]\n",
    "        f[0] = [0, 0, 0]\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i >= n:\n",
    "                return 0\n",
    "            return max(0, k - nums[i]) + min(dfs(i + 1), dfs(i + 2), dfs(i + 3))\n",
    "        \n",
    "        res = min(dfs(0), dfs(1), dfs(2))\n",
    "        dfs.cache_clear()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementOperations(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(idx):\n",
    "            if idx == n:\n",
    "                return 0\n",
    "            \n",
    "            res = inf\n",
    "            t = max(k - nums[idx], 0)\n",
    "            for i in range(idx, min(idx + 3, n)):\n",
    "                res = min(res, t + dfs(i + 1))\n",
    "\n",
    "            return res\n",
    "\n",
    "        ans = min(dfs(0), dfs(1), dfs(2))\n",
    "        dfs.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementOperations(self, a: List[int], k: int) -> int:\n",
    "        n = len(a)\n",
    "        @cache\n",
    "        def dfs(i, p):\n",
    "            if i == n: return 0\n",
    "            x = a[i]\n",
    "            if x >= k: return dfs(i + 1, 1)\n",
    "            if p == 3: return k - x + dfs(i + 1, 1)\n",
    "            return min(k - x + dfs(i + 1, 1), dfs(i + 1, p + 1))\n",
    "        res = dfs(0, 1)\n",
    "        dfs.cache_clear()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementOperations(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i <= 1:\n",
    "                return 0\n",
    "            a, b, c = nums[i - 2], nums[i - 1], nums[i]\n",
    "            if max([a, b, c]) >= k:\n",
    "                return dfs(i - 1)\n",
    "            return min([dfs(i - 3) + k - a, dfs(i - 2) + k - b, dfs(i - 1) + k - c])\n",
    "        return dfs(n - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementOperations(self, nums: List[int], k: int) -> int:\n",
    "        l = len(nums)\n",
    "        @cache\n",
    "        def dfs(cur):\n",
    "            if cur > l- 3:\n",
    "                return 0\n",
    "            if max(nums[cur:cur + 3]) >= k:\n",
    "                return dfs(cur + 1)\n",
    "            if max(nums[cur:cur + 3]) == nums[cur + 2]:\n",
    "                return dfs(cur + 3) + k - nums[cur + 2]\n",
    "            return min(dfs(cur + 1) + k - nums[cur], dfs(cur + 2) + k - nums[cur + 1], dfs(cur + 3) + k - nums[cur + 2])\n",
    "        return dfs(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "from typing import List, Tuple, Optional\n",
    "from collections import defaultdict, Counter\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "\n",
    "MOD = int(1e9 + 7)\n",
    "INF = int(1e20)\n",
    "\n",
    "# 给你一个下标从 0 开始、长度为 n 的整数数组 nums ，和一个整数 k 。\n",
    "\n",
    "# 你可以执行下述 递增 运算 任意 次（可以是 0 次）：\n",
    "\n",
    "# 从范围 [0, n - 1] 中选则一个下标 i ，并将 nums[i] 的值加 1 。\n",
    "# 如果数组中任何长度 大于或等于 3 的子数组，其 最大 元素都大于或等于 k ，则认为数组是一个 美丽数组 。\n",
    "\n",
    "# 以整数形式返回使数组变为 美丽数组 需要执行的 最小 递增运算数。\n",
    "\n",
    "\n",
    "# 子数组是数组中的一个连续 非空 元素序列。\n",
    "\n",
    "\n",
    "def min(a, b):\n",
    "    return a if a < b else b\n",
    "\n",
    "\n",
    "def max(a, b):\n",
    "    return a if a > b else b\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementOperations(self, nums: List[int], k: int) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(index: int, ok1: bool, ok2: bool) -> int:\n",
    "            if index == n:\n",
    "                return 0\n",
    "\n",
    "            cur = nums[index]\n",
    "            # 当前加\n",
    "            res = dfs(index + 1, ok2, True) + max(0, k - cur)\n",
    "\n",
    "            # 当前不加\n",
    "            curOk = cur >= k\n",
    "            if ok1 or ok2 or curOk:\n",
    "                res = min(res, dfs(index + 1, ok2, curOk))\n",
    "\n",
    "            return res\n",
    "\n",
    "        n = len(nums)\n",
    "        res = dfs(0, True, True)\n",
    "        dfs.cache_clear()\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementOperations(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i >= n: return 0\n",
    "            if nums[i] >= k:\n",
    "                return min(dfs(i + 1), dfs(i + 2), dfs(i + 3))\n",
    "            return min(dfs(i + 1), dfs(i + 2), dfs(i + 3)) + k - nums[i]\n",
    "        return min(dfs(0), dfs(1), dfs(2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementOperations(self, nums: List[int], k: int) -> int:\n",
    "        n=len(nums)\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i<0:\n",
    "                return 0\n",
    "\n",
    "            res = max(0,k-nums[i])\n",
    "            if i==0:\n",
    "                return res\n",
    "            \n",
    "            ans = min(dfs(i-1),dfs(i-2),dfs(i-3))+res\n",
    "            return ans\n",
    "\n",
    "        \n",
    "        return min(dfs(n-1),dfs(n-2),dfs(n-3))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementOperations(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i+2 >= n:\n",
    "                return 0\n",
    "            return min(max(0, k-nums[i])+dfs(i+1), \n",
    "                       max(0, k-nums[i+1])+dfs(i+2),\n",
    "                       max(0, k-nums[i+2])+dfs(i+3))\n",
    "        return dfs(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementOperations(self, a: List[int], k: int) -> int:\n",
    "        n = len(a)\n",
    "        b = [0 if j>=k else k-j for j in a ]\n",
    "        @cache \n",
    "        def f(j):\n",
    "            if j<=1:\n",
    "                return 0 \n",
    "            if j==2:\n",
    "                return min(b[:3])\n",
    "            return min(b[j]+f(j-1), b[j-1]+f(j-2), b[j-2]+f(j-3))\n",
    "        return f(n-1)\n",
    "            \n",
    "                \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementOperations(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        @lru_cache(None)\n",
    "        def dfs(st):\n",
    "            if st >= n:\n",
    "                return 0\n",
    "            ans = float('inf')\n",
    "            for i in range(st, st+3):\n",
    "                ans = min(ans, max(0, k-nums[i]) + dfs(i + 1)) \n",
    "            return ans\n",
    "        \n",
    "        nums += [k] * 3\n",
    "        # for i in range(n):\n",
    "        #     print(i, dfs(i))\n",
    "        return dfs(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @cache\n",
    "    def f(self,pos,k):\n",
    "        if pos < 3:\n",
    "            return max(k - self.nums[pos],0)\n",
    "        return min(self.f(pos-1,k),self.f(pos-2,k),self.f(pos-3,k))+max(k - self.nums[pos],0)\n",
    "    def minIncrementOperations(self, nums: List[int], k: int) -> int:\n",
    "        nums.append(k)\n",
    "        self.nums = nums\n",
    "        return self.f(len(nums)-1,k)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementOperations(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        @cache\n",
    "        def dp(p,t):\n",
    "            if p >= n:\n",
    "                return 0\n",
    "            if p >= n - 2 and t:\n",
    "                return 0\n",
    "            ans = inf\n",
    "            ans = min(dp(p + 1, 1) + max(k - nums[p], 0), ans)\n",
    "            if p + 1 < n:\n",
    "                ans = min(dp(p + 2, 1) + max(k - nums[p + 1], 0), ans)\n",
    "            if p + 2 < n:\n",
    "                ans = min(dp(p + 3, 1) + max(k - nums[p + 2], 0), ans)\n",
    "            # print(p, ans)\n",
    "            return ans\n",
    "        return dp(0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementOperations(self, nums: List[int], k: int) -> int:\n",
    "        # 假设已知i到n-1的步数，可以推i-1是否为最有解\n",
    "        n = len(nums)\n",
    "        @cache\n",
    "        def dfs(i,n):\n",
    "            if i>n-3:\n",
    "                return 0\n",
    "            # 选0 1 2 的不同代价\n",
    "            c1 = k-nums[i] if k>nums[i] else 0\n",
    "            c2 = k-nums[i+1] if k>nums[i+1] else 0\n",
    "            c3 = k-nums[i+2] if k>nums[i+2] else 0\n",
    "            return min(min(c1+dfs(i+1,n),c2+dfs(i+2,n)),c3+dfs(i+3,n))\n",
    "        return dfs(0,n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementOperations(self, nums: List[int], k: int) -> int:\n",
    "        @cache\n",
    "        def f(i):\n",
    "            if i < 2: return 0\n",
    "            return min(f(j-1)+max(0,k-nums[j]) for j in range(i,max(i-3,-1),-1))\n",
    "        return f(len(nums)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementOperations(self, nums: List[int], k: int) -> int:\n",
    "        @cache\n",
    "        def dfs(prev, left):\n",
    "            if n-1-prev <= 2:\n",
    "                return 0\n",
    "            if n-1-left <= 2:\n",
    "                return max(0, k - max(nums[left:]))\n",
    "            res = float(\"inf\")\n",
    "            for i in range(3):\n",
    "                res = min(res, max(0, k-nums[left+i]) + dfs(left+i, left+i+1))\n",
    "            return res\n",
    "\n",
    "        n = len(nums)\n",
    "        \n",
    "        return dfs(-3, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementOperations(self, nums: List[int], k: int) -> int:\n",
    "        acc =0\n",
    "        n = len(nums)\n",
    "        def isGood(idx):\n",
    "            if 0<=idx<n and nums[idx] >=k:\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "        @cache\n",
    "        def dfs(i,p):\n",
    "            if i >=n:\n",
    "                return 0\n",
    "            mn = 10**20\n",
    "            if isGood(i-2) or isGood(i-1) or isGood(i) or i <2:\n",
    "                mn =min(mn, dfs(i+1,tuple([i,i-3,10**9] +nums[i-2:i])))\n",
    "            else:\n",
    "                if i>=2:\n",
    "                    a = k - nums[i-2]\n",
    "                    nums[i-2]=k\n",
    "                    mn =min(mn, a + dfs(i+1,tuple([i,i-2,10**9] +nums[i-2:i])))\n",
    "                    nums[i-2]-=a\n",
    "                if i >=1:\n",
    "                    a = k - nums[i-1]\n",
    "                    nums[i-1] = k\n",
    "                    mn = min(mn,a + dfs(i+1,tuple([i,i-1,10**9] +nums[i-2:i])))\n",
    "                    nums[i-1] -=a\n",
    "                a = k - nums[i]\n",
    "                nums[i] =k\n",
    "                mn = min(mn,dfs(i+1,tuple([i,i,10**9] +nums[i-2:i]))+a)\n",
    "                nums[i] -=a\n",
    "                # if i ==1:\n",
    "                #     a = k - nums[i+1]\n",
    "                #     nums[i+1] = k\n",
    "                #     mn = min(mn,dfs(i+1)+a)\n",
    "                #     nums[i+1] -=a\n",
    "                # if i ==0:\n",
    "                #     a = k-nums[i+2]\n",
    "                #     nums[i+2] = k \n",
    "                #     mn = min(mn,dfs(i+1)+a)\n",
    "                #     nums[i+2] -=a\n",
    "            return mn\n",
    "                \n",
    "        return dfs(0,-3)   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementOperations(self, nums, k: int) -> int:\n",
    "        cache = {}\n",
    "\n",
    "        def dfs(cur, distance):\n",
    "            if cur in cache:\n",
    "                if distance in cache[cur]:\n",
    "                    return cache[cur][distance]\n",
    "            if cur not in cache:\n",
    "                cache[cur] = {}\n",
    "            if cur == len(nums):\n",
    "                return 0\n",
    "            if distance > 2:\n",
    "                m = dfs(cur+1, 1)+max(0, k-nums[cur])\n",
    "                cache[cur][distance] = m\n",
    "                return m\n",
    "            m = dfs(cur+1, 1)+max(0, k-nums[cur])\n",
    "            n = dfs(cur+1, distance+1)\n",
    "            m = min(m, n)\n",
    "            cache[cur][distance] = m\n",
    "            return m\n",
    "        a = dfs(2, 1)+max(0, k-nums[1])  # nums[1]>K\n",
    "        b = a\n",
    "        c = a\n",
    "        if(k-nums[1] > 0):\n",
    "            b = dfs(2, 2) + max(0, k-nums[0])  # nums[0]>K\n",
    "            if k-nums[0] > 0:\n",
    "                c = dfs(2, 3)  # nums[0]&nums[1]<K\n",
    "        a = min(a, b)\n",
    "        a = min(a, c)\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementOperations(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        @cache\n",
    "        def dfs(i, fill):\n",
    "            if i < 0:\n",
    "                return inf if fill else 0\n",
    "            if i <= 2:\n",
    "                if fill:\n",
    "                    return max(0, k - nums[i])\n",
    "                else:\n",
    "                    return min(dfs(i-1, True), dfs(i-2, True))\n",
    "            if fill:\n",
    "                return max(0, k - nums[i]) + min(dfs(i-1, False), dfs(i-1, True))\n",
    "            else:\n",
    "                return min(dfs(i-1, True), dfs(i-2, True))\n",
    "        # for i in range(n):\n",
    "        #     print(dfs(i, False), dfs(i, True))\n",
    "        return min(dfs(n-1, True), dfs(n-1, False))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementOperations(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        @cache\n",
    "        def dfs(i, isK):\n",
    "            if i < 0: return 0\n",
    "            if isK: return max(k - nums[i], 0) + min(\n",
    "                dfs(i - 1, 1),\n",
    "                dfs(i - 1, 0)\n",
    "            )\n",
    "\n",
    "            return min(\n",
    "                dfs(i - 1, 1), \n",
    "                dfs(i - 2, 1)\n",
    "            )\n",
    "            \n",
    "        return min(dfs(n - 1, 1), dfs(n - 1, 0))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementOperations(self, nums: List[int], k: int) -> int:\n",
    "        \n",
    "        @cache\n",
    "        def dfs(a, b, i):\n",
    "            c = nums[i]\n",
    "            mx = max(a, b, c)\n",
    "            if i == len(nums) - 1:\n",
    "                return k - mx if mx < k else 0\n",
    "            \n",
    "            if mx < k:\n",
    "                return min(\n",
    "                    k-a + dfs(b, c, i+1),\n",
    "                    k-b + dfs(k, c, i+1),\n",
    "                    k-c + dfs(b, k, i+1)\n",
    "                )\n",
    "            else:\n",
    "                return dfs(b, c, i+1)\n",
    "        return dfs(nums[0], nums[1], 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementOperations(self, nums: List[int], k: int) -> int:\n",
    "        n=len(nums)\n",
    "        @cache\n",
    "        def f(i,j):\n",
    "            if i<0:\n",
    "                return 0\n",
    "            if nums[i]>=k:\n",
    "                res=f(i-1,0)\n",
    "            else:\n",
    "                res=f(i-1,0)+k-nums[i]\n",
    "                if j<2:\n",
    "                    res=min(res,f(i-1,j+1))\n",
    "            return res\n",
    "        return f(n-1,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementOperations(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        @cache\n",
    "        def dfs(i:int, j:int)->int:\n",
    "            if i < 0:\n",
    "                return 0\n",
    "            if nums[i] >= k:\n",
    "                res = dfs(i-1, 0)\n",
    "            else:\n",
    "                res = dfs(i-1, 0) + k - nums[i]  #变\n",
    "                if j < 2:\n",
    "                    res = min(res, dfs(i-1,j+1))\n",
    "            return res\n",
    "        return dfs(n-1, 0)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "任何长度大于或等于3的子数组\n",
    "\n",
    "任何长度等于3的子数组\n",
    "包含至少一个 >= k 的数\n",
    "\n",
    "\n",
    "选一个子序列，子序列的所有元素都需要变成 >= k的数\n",
    "子序列的相邻元素，不能间隔太大(子系列相邻元素下标差最大为3)。 打家劫舍\n",
    "\n",
    "DP 选或不选 枚举选哪个\n",
    "\n",
    "\n",
    "如何消除 [后效性]\n",
    "\n",
    "\n",
    "定义 dfs(i, j) 表示现在要处理 nums[0] 到 nums[i] 这段子数组\n",
    "并且 nums[i] 右边有 j 个没有变大的数。\n",
    "\n",
    "选： dfs(i, j) = difs(i-1, 0) + max(k-x, 0)\n",
    "不选： 当j < 2时刻： dfs(i-1, j+1) \n",
    "当 j > 2 时刻， 必须选\n",
    "\n",
    "递归边界： 当 i < 0 ， 返回 0\n",
    "递归入口： dfs(n-1, 0)\n",
    "\n",
    "'''\n",
    "class Solution:\n",
    "    def minIncrementOperations(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        @cache\n",
    "        def dfs(i: int, j: int) -> int:\n",
    "            if i < 0:\n",
    "                return 0\n",
    "            res = dfs(i-1, 0) + max(k-nums[i], 0) # 选\n",
    "            if nums[i] < k and j < 2:\n",
    "                res = min(dfs(i-1, j+1), res) # 不选\n",
    "            return res\n",
    "        return dfs(n-1, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementOperations(self, nums: List[int], k: int) -> int:\n",
    "        #定义 dfs(i, j)表示现在要处理nums[0] 到 nums[i] 这段子数组，并且nums[i]右边有j个没有变大的数\n",
    "        n = len(nums)\n",
    "\n",
    "        #记忆化搜索\n",
    "        @cache\n",
    "        def dfs(i: int, j: int) -> int:\n",
    "            #递归出口\n",
    "            if i == -1:\n",
    "                return 0\n",
    "            if j == 2:      #必须要处理当前nums[i]\n",
    "                return max(k - nums[i], 0) + dfs(i - 1, 0)\n",
    "            #不处理当前nums[i]和处理当前nums[i]中的最小值\n",
    "            return min(dfs(i - 1, j + 1), max(k - nums[i], 0) + dfs(i - 1, 0))\n",
    "\n",
    "        return dfs(n - 1, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementOperations(self, nums: List[int], k: int) -> int:\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i,j):\n",
    "            # 0到i范围 ，右边有j个小于k的数\n",
    "            if i<0:\n",
    "                return 0\n",
    "            if j==2:\n",
    "                return dfs(i-1,0)+ max(0, k-nums[i])\n",
    "            else:\n",
    "                return min(dfs(i-1,0)+max(0,k-nums[i]), dfs(i-1,j+1))\n",
    "        \n",
    "        n = len(nums)\n",
    "        return dfs(n-1,0)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
